import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
* 算法：遍历迭代
*
* 二叉搜索树的性质：对于任意节点 root 而言，左子树（如果存在）上所有节点的值均小于 root.val，
* 右子树（如果存在）上所有节点的值均大于 root.val
* 思路：
* 1. 给一个指针，遍历整个树
* 2. 重点：先判断大小，在进行插入


* */
public class Solution_1 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while (pos != null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else {
                    pos = pos.left;
                }
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else {
                    pos = pos.right;
                }
            }
        }
        return root;

    }
}
